\section{C\'odigo Fuente}

A continuación se incluyen los principales segmentos del código fuente del programa.\\
Adicionalmente, todos los archivos se encuentran en el archivo adjunto a este documento.

\subsection{Programa General}

{\footnotesize

\begin{verbatim}
 #!/bin/bash

# Cantidad de argumentos esperados
CANT_ARGS=2

if [ $# -ne $CANT_ARGS ]
then
	echo "USO: $0 'regex' archivo.txt" >&2
	exit 1
fi

if [ -z "$1" ]
then
	echo "ERROR: Se debe indicar una expresión regular no vacía." >&2
	exit 1
fi

if [ ! -f $2 -o -z "`file $2 | grep -oP 'text'`" ]
then
	echo "ERROR: El archivo no existe o no es un archivo de texto válido." >&2
	exit 1
fi

if [ ! -r $2 ]
then
	echo "ERROR: No se tiene permiso de lectura sobre el archivo indicado." >&2
	exit 1
fi

java -cp "$PWD"/tl_tp/bin:"$PWD"/target/tplenguajes-0.1-jar-with-dependencies.jar tl.RegexEngine "$1" "$2"

exit 0
\end{verbatim}
}

\subsection{Clase Principal}

{\footnotesize
\begin{verbatim}
package tl;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.antlr.runtime.ANTLRStringStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.tree.CommonTree;

import tplenguajes.TLexer;
import tplenguajes.TParser;
import tplenguajes.TParser.s_return;
import tplenguajes.grafo.AFD;
import tplenguajes.grafo.AFND;

public class RegexEngine {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		if (args.length < 2){ //Se tiene que recibir dos parámetros
			System.err.println("Uso: RegexEngine 'regex' archivo.txt");
			System.exit(1);
		}
	
		TLexer lexer = new TLexer();
		AFD<String> automaton = null;

		//Se parsea la expresión regular recibida
		try{
			automaton = parseRegex(args[0], lexer);
		}catch(Exception e){
			System.err.println("ERROR: La expresión regular ingresada '" + args[0] + "' no es válida.");
			System.exit(1);
		}
		
		try{
			FileInputStream fstream	= new FileInputStream(args[1]);
			DataInputStream in 		= new DataInputStream(fstream);
			BufferedReader  br 		= new BufferedReader(new InputStreamReader(in));
			String strLine;
			//Se lee el archivo línea por línea
			while ((strLine = br.readLine()) != null)   {
				Iterable<String> iterableString = getIterableString(strLine);
				if (automaton.acceptsString(iterableString))
					System.out.println(strLine);
			}
		}catch (IOException e) {
			System.err.println("ERROR: Hubo un problema al intentar abrir el archivo de texto ("+ e + ").");
			e.printStackTrace();
		}catch (Exception e){
			System.err.println("ERROR: Hubo un problema desconocido (" + e + ").");
			e.printStackTrace();
		}		
	}

	public static AFD<String> parseRegex(String source, TLexer lexer) throws Exception {
			//Parseando regex
			lexer.setCharStream(new ANTLRStringStream(source));

			CommonTokenStream tokens = new CommonTokenStream(lexer);

			TParser parser = new TParser(tokens);
			s_return psrReturn = parser.s();

			CommonTree t = (CommonTree) psrReturn.getTree();

			// Se define el alfabeto
			Set<String> alphabet = new HashSet<String>();
			for (char c = 'a'; c < 'z' + 1; c++)
				alphabet.add(Character.toString(c));
			for (char c = 'A'; c < 'Z' + 1; c++)
				alphabet.add(Character.toString(c));
			for (char c = '0'; c < '9' + 1; c++)
				alphabet.add(Character.toString(c));
			alphabet.add(" ");
			
			//Generando AFND
			AFND<String> afnd = new AFND<String>(t, alphabet);
			//Convirtiendo a AFD
			AFD<String> afd = new AFD<String>(afnd);
			
			return afd; 
	}

	private static List<String> getIterableString(String string){
		List<String> iterableString = new ArrayList<String>();
		
		for(int i=0; i<string.length(); i++){
			iterableString.add(string.substring(i, i+1));
		}
		
		return iterableString;
	}
	
}
\end{verbatim}
}

\subsection{Autómatas}

\subsubsection{Autómata Finito No-Determinístico con Transiciones Lambda}

{\footnotesize
\begin{verbatim}
package tplenguajes.grafo;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

import org.antlr.runtime.tree.CommonTree;

import tplenguajes.TParser;

public class AFND<T> extends FiniteAutomata<T>
{
	public AFND(CommonTree ast, Set<T> alphabet)
	{
		super(alphabet);
		
		AutomataState end = new AutomataState();
		addVertex(end);
		end.setAsFinal();
		
		int token = ast.getToken().getType();
		
		if ( token == TParser.OR )
		{
			FiniteAutomata<T> left = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			FiniteAutomata<T> right = new AFND<T>((CommonTree)ast.getChild(1),alphabet);
			
			this.addAutomata(left);
			this.addAutomata(right);
			
			addLambdaTransition(this.getRoot(), left.getRoot());
			addLambdaTransition(this.getRoot(), right.getRoot());
			
			for ( AutomataState leftEnd : left.getFinalStates() )
				addLambdaTransition(leftEnd, end);
			
			for ( AutomataState rightEnd : right.getFinalStates() )
				addLambdaTransition(rightEnd, end);
			
			unsetFinals(left);
			unsetFinals(right);
		}
		else if ( token == TParser.CL )
		{
			FiniteAutomata<T> expression = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			
			this.addAutomata(expression);
			
			addLambdaTransition(this.getRoot(), end);
			addLambdaTransition(this.getRoot(), expression.getRoot());
			
			for ( AutomataState exprEnd : expression.getFinalStates() )
			{
				addLambdaTransition(exprEnd, end);
				addLambdaTransition(exprEnd, expression.getRoot());
			}
			
			unsetFinals(expression);
		}
		else if ( token == TParser.CLP )
		{
			FiniteAutomata<T> expression = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			
			this.addAutomata(expression);
			
			addLambdaTransition(this.getRoot(), expression.getRoot());
			
			for ( AutomataState exprEnd : expression.getFinalStates() )
			{
				addLambdaTransition(exprEnd, end);
				addLambdaTransition(exprEnd, expression.getRoot());
			}
			
			unsetFinals(expression);
		}
		else if ( token == TParser.OPC )
		{
			FiniteAutomata<T> expression = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			
			this.addAutomata(expression);
			
			addLambdaTransition(this.getRoot(), end);
			addLambdaTransition(this.getRoot(), expression.getRoot());
			
			for ( AutomataState exprEnd : expression.getFinalStates() )
				addLambdaTransition(exprEnd, end);
			
			unsetFinals(expression);
		}
		else if ( token == TParser.ERCONCAT && ast.getChildCount() == 2 )
		{
			FiniteAutomata<T> left = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			FiniteAutomata<T> right = new AFND<T>((CommonTree)ast.getChild(1),alphabet);
			
			this.addAutomata(left);
			this.addAutomata(right);
			
			addLambdaTransition(this.getRoot(), left.getRoot());
			
			for ( AutomataState leftEnd : left.getFinalStates() )
				addLambdaTransition(leftEnd, right.getRoot());
			
			for ( AutomataState rightEnd : right.getFinalStates() )
				addLambdaTransition(rightEnd, end);
			
			unsetFinals(left);
				unsetFinals(right);
		}
		else if ( token == TParser.ER || ( token == TParser.ERCONCAT && ast.getChildCount() == 1 ) )
		{
			FiniteAutomata<T> expression = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			
			this.addAutomata(expression);
			
			addLambdaTransition(this.getRoot(), expression.getRoot());
			
			for ( AutomataState exprEnd : expression.getFinalStates() )
				addLambdaTransition(exprEnd, end);
			
			unsetFinals(expression);
		}
		else if ( token == TParser.ANY )
		{
			for ( T transition : getAlphabet() )
				addStateTransition(this.getRoot(), end, (String)transition);
		}
		else if ( token == TParser.CAR )
		{
			String transition = ast.toString();
			
			addStateTransition(this.getRoot(), end, transition);
		}
		else
			System.err.println("Unhandled token "+token+" building AFND from tree");
	}
	
	public Set<AutomataState> getEpsilonClosure(Set<AutomataState> initialClosure)
	{
		Set<AutomataState> closure = new HashSet<AutomataState>(initialClosure);
		Stack<AutomataState> stack = new Stack<AutomataState>();
		
		for (AutomataState subState : initialClosure)
			stack.push(subState);
		
		while (!stack.isEmpty())
		{
			AutomataState subState = stack.pop();
			
			for ( Edge<AutomataState> e : getOutgoingEdges(subState) )
				if ( e instanceof LambdaTransition )
					if ( !closure.contains(e.getTarget()) )
					{
						closure.add(e.getTarget());
						stack.push(e.getTarget());
					}
		}
		
		return closure;
	}
	
	
	public Set<AutomataState> getTargets(Set<AutomataState> sources, T transition)
	{
		Set<AutomataState> targets = new HashSet<AutomataState>();
		
		for ( AutomataState state : sources )
			for ( Edge<AutomataState> edge : getOutgoingEdges(state) )
				if ( !(edge instanceof LambdaTransition) )
					if ( getLabel(edge).equals(transition) )
						targets.add(edge.getTarget());
		
		return targets;
	}
	
	
	public boolean isFinalClosure(Set<AutomataState> closure)
	{
		for ( AutomataState state : closure )
			if ( state.isFinal() )
				return true;
		
		return false;
	}
	
	private void addAutomata(FiniteAutomata<T> automata)
	{
		for (AutomataState v : automata.getVertices() )
			addVertex(v);
		
		for (Edge<AutomataState> e : automata.getEdges() )
			addEdge(automata.getEdgeSource(e), automata.getEdgeTarget(e), e);
	}
	
	private void unsetFinals(FiniteAutomata<T> automata)
	{
		for (AutomataState v : automata.getVertices() )
			v.unsetAsFinal();
	}
	
	private boolean addLambdaTransition(AutomataState src, AutomataState dst)
	{
		return this.addEdge(src, dst, new LambdaTransition(src,dst));
	}
	
	
	private boolean addStateTransition(AutomataState src, AutomataState dst, String transition)
	{
		return this.addEdge(src, dst, new StateTransition<String>(src, dst, transition));
	}
	
}
\end{verbatim}
}


\subsubsection{Autómata Finito Determinístico}

{\footnotesize
\begin{verbatim}
package tplenguajes.grafo;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class AFD<T> extends FiniteAutomata<T>
{
	public AFD(AFND<T> afnd)
	{
		super(afnd.getAlphabet());
		
		conversionIterativa(afnd);
	}
	
	public boolean acceptsString(Iterable<T> string)
	{
		AutomataState currentState = this.getRoot();
		
		for ( T transition : string )
		{
			currentState = getEdges(currentState).getTarget(transition);
			if ( currentState == null ) return false;
		}
		
		if ( !currentState.isFinal() )
			return false;
		
		return true;
	}
	
	private void conversionIterativa(AFND<T> afnd)
	{
		Map<AutomataState,Set<AutomataState>> stateMap = new HashMap<AutomataState, Set<AutomataState>>();
		
		Stack<AutomataState> stack = new Stack<AutomataState>();
		
		Set<AutomataState> rootSet = new HashSet<AutomataState>(); rootSet.add(afnd.getRoot());
		Set<AutomataState> initialClosure = afnd.getEpsilonClosure(rootSet);
		
		stateMap.put(this.getRoot(), initialClosure);
		stack.push(this.getRoot());
		if( afnd.isFinalClosure(initialClosure) )
			this.getRoot().setAsFinal();
		
		while (!stack.isEmpty())
		{
			AutomataState state = stack.pop();
			
			// TODO Me parece bastante poco performante iterar sobre todo el alfabeto
			// sera mejor armar el conjunto de posibles transiciones del conjunto de estados?
			for ( T transition : getAlphabet() )
			{
				Set<AutomataState> sources = stateMap.get(state);
				Set<AutomataState> targets = afnd.getTargets(sources, transition);
				
				if (!targets.isEmpty())
				{
					Set<AutomataState> potentialNewClosure = afnd.getEpsilonClosure(targets);
					
					AutomataState potentialNewState = stateThatContains(potentialNewClosure, stateMap);
					
					if ( potentialNewState == null )
					{
						potentialNewState = new AutomataState();
						this.addVertex(potentialNewState);
						
						stateMap.put(potentialNewState, potentialNewClosure);
						stack.push(potentialNewState);
						
						if( afnd.isFinalClosure(potentialNewClosure) )
							potentialNewState.setAsFinal();
					}
					
					addStateTransition(state, potentialNewState, transition);
				}
			}
		}
	}
	
	private AutomataState stateThatContains(Set<AutomataState> closure, Map<AutomataState,Set<AutomataState>> states)
	{
		for ( AutomataState key : states.keySet() )
			if (closure.equals(states.get(key)))
				return key;
		
		return null;
	}
	
	private boolean addStateTransition(AutomataState src, AutomataState dst, T transition)
	{
		return this.addEdge(src, dst, new StateTransition<T>(src, dst, transition));
	}
	
	@Override protected Edges getNewEdges() { return new AFDEdges(); }
	@Override protected AFDEdges getEdges(AutomataState v) { return (AFDEdges)super.getEdges(v); }
	
	protected class AFDEdges extends Edges
	{
		private Map<T,Edge<AutomataState>> incoming = new HashMap<T, Edge<AutomataState>>();
		private Map<T,Edge<AutomataState>> outgoing = new HashMap<T, Edge<AutomataState>>();
        
		@Override public void addIncomingEdge(Edge<AutomataState> e) { incoming.put(getLabel(e),e); }
		@Override public void addOutgoingEdge(Edge<AutomataState> e) { outgoing.put(getLabel(e),e); }
		
		@Override public void removeIncomingEdge(Edge<AutomataState> e) { incoming.remove(getLabel(e)); }
		@Override public void removeOutgoingEdge(Edge<AutomataState> e) { outgoing.remove(getLabel(e)); }
        
        @Override public Set<Edge<AutomataState>> getIncoming() { return getValueSet(incoming); }
        @Override public Set<Edge<AutomataState>> getOutgoing() { return getValueSet(outgoing); }
		
        public AutomataState getTarget(T transition)
        {
        	Edge<AutomataState> edge = outgoing.get(transition);
        	return (edge==null) ? null : edge.getTarget();
        }
        
		private Set<Edge<AutomataState>> getValueSet(Map<T, Edge<AutomataState>> map)
		{
			Set<Edge<AutomataState>> result = new HashSet<Edge<AutomataState>>();
			
			for ( T t : map.keySet() )
				result.add(map.get(t));
			
			return result;
		}
		
		private T getLabel(Edge<AutomataState> e) { return ((StateTransition<T>)e).getLabel(); }
	}
} 
\end{verbatim}
}